#pragma onec

#include <assert.h>

template<class K, class V>
struct AVLtreeNode
{
    AVLtreeNode<K,V>* _left;
    AVLtreeNode<K,V>* _right;
    AVLtreeNode<K,V>* _parent;
    int _bf;//
    pair<K,V> _kv;

    AVLtreeNode(const pair<K,V>& kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_bf(0)
    ,_kv(kv)
    {}
};

template<class K, class V>
class AVLTree
{
    typedef  AVLtreeNode<K,V> Node;
public:
    bool insert(const paif<K,V>& kv)
    {
        if(_root == nullptr)
        {
            _root = new Node(kv)
            return true;
        }

        Node* parent = nullptr;
        Node* cur = _root;
        while(cur)
        {
            if(cur->_kv.first < kv.first)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if(cur->_kv.first > kv.first)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
        }

        cur = new Node(kv);
        if(parent->_kv.first < kv.first)
        {
            parent->_right = cur;
        }
        else
        {
            parent->_left = cur;
        }
        cur->_parent = parent;

        while(parent)
        {
            if(cur == parent->_left)
            {
                parent->_bf--;
            }
            else
            {
                parent->_bf++;
            }

            if(parent->_bf == 0)
            {
                break;
            }
            else if(parent->_bf == 1 || parent->_bf == -1)
            {
                cur = cur->_parent;
                parent = parent->_parent;
            }
            else if(parent->_bf == 2 || parent->_bf == -2)
            {
                if(parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent); 
                }
                else if(parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if(parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                else
                {
                    RotateRL(parent);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }
private:
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if(subRL)
            subRL->_parent = parent;

        subR->_left = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = subR;
        if(parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if(ppnode->_left == parent)
            {
                ppnode->_left = subR;
            }
            else
            {
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        parent->_bf = 0;
        subR->_bf = 0;
    }

    void RotateL(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if(subLR)
            subLR->_parent = parent;

        subL->_right = parent;
        Node* ppnode = parent->_parent;
        parent->_parent = subL;
        if(parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if(ppnode->_left == parent)
            {
                ppnode->_left = subL;
            }
            else
            {
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        subL->_bf = 0;
        parent->_bf = 0;
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);

        if(bf == -1)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        }
        else if(bf == 1)
        {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        }
        else if(bf == 0)
        {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subL->_left;

        int bf = subRL->_bf;

        RotateR(subR);
        RotateL(parent);

        subRL->_bf = 0;

        if(bf == 1)
        {
            subR->_bf == 0;
            parent->_bf = -1;
        }
        else if(bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
        }
        else
        {
            parent->_bf = 0;
            subR->_bf = 0;
        }

    }
private:
    Node* _root;
};

void test()
{
    AVLTree<int,int> t;
    int a[] = {16,3,7,11,9,26,18,14,15};
    for(auto e:a)
    {
        t.insert(make_pair(e,e));
    }

}

